#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int count(struct TreeNode *root)
{
    if (!root) {
        return 0;
    }

    return 1 + count(root->left) + count(root->right);
}

void dfs(struct TreeNode *root, int *arr, int *pos)
{
    if (!root) {
        return;
    }

    dfs(root->left, arr, pos);
    arr[*pos] = root->val;
    (*pos)++;
    dfs(root->right, arr, pos);
}

int binarySearch(const int *arr, int arrSize, int target)
{
    int left = 0, right = arrSize - 1, res = arrSize;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            res = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return res;
}

int **closestNodes(struct TreeNode *root, int *queries, int queriesSize, int *returnSize, int **returnColumnSizes)
{
    int nodesNum = count(root);
    int *arr = (int *)malloc(sizeof(int) * nodesNum);
    int pos = 0;
    dfs(root, arr, &pos);

    int **res = (int **)malloc(sizeof(int *) * queriesSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * queriesSize);
    for (int i = 0; i < queriesSize; i++) {
        res[i] = (int *)malloc(sizeof(int) * 2);
        (*returnColumnSizes)[i] = 2;

        int val = queries[i];
        int maxVal = -1, minVal = -1;
        int index = binarySearch(arr, nodesNum, val);
        if (index != nodesNum) {
            maxVal = arr[index];
            if (arr[index] == val) {
                minVal = arr[index];
                res[i][0] = minVal;
                res[i][1] = maxVal;
                continue;
            }
        }
        if (index != 0) {
            minVal = arr[index - 1];
        }
        res[i][0] = minVal;
        res[i][1] = maxVal;
    }
    *returnSize = queriesSize;
    return res;
}

void testClosestNodes()
{
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 6;

    root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->left->val = 1;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->right->val = 4;
    root->left->right->left = NULL;
    root->left->right->right = NULL;

    root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->val = 13;
    root->right->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->left->val = 9;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->right->val = 15;
    root->right->right->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->right->left->val = 14;
    root->right->right->left->left = NULL;
    root->right->right->left->right = NULL;
    root->right->right->right = NULL;

    int queries[] = { 2, 5, 16 };
    int returnSize;
    int *returnColumnSizes;

    int **result = closestNodes(root, queries, sizeof(queries) / sizeof(queries[0]), &returnSize, &returnColumnSizes);

    for (int i = 0; i < returnSize; i++) {
        printf("[%d, %d]\n", result[i][0], result[i][1]);
        free(result[i]);
    }

    free(result);
    free(returnColumnSizes);
}

int main()
{
    testClosestNodes();
    return 0;
}